package com.yang.Hash_;

import java.util.HashMap;

public class LeetCode454 {
    public static void main(String[] args){
        SolutionLeetCode454 solutionLeetCode454 = new SolutionLeetCode454();
        String s1 = "aaa";
        String s2 = "aa" + new String("a");
        System.out.println(s2);
        System.out.println(s2.intern());
        System.out.println(s1.intern().equals(s2));
    }
}

// 要点思路：一采用分为两组，HashMap 存一组，另一组和 HashMap 进行比对。
//这样的话情况就可以分为三种：
//
//    HashMap 存一个数组，如 A。然后计算三个数组之和，如 BCD。时间复杂度为：O(n)+O(n^3)，得到 O(n^3).
//    HashMap 存三个数组之和，如 ABC。然后计算一个数组，如 D。时间复杂度为：O(n^3)+O(n)，得到 O(n^3).
//    HashMap存两个数组之和，如AB。然后计算两个数组之和，如 CD。时间复杂度为：O(n^2)+O(n^2)，得到 O(n^2).
//
//根据第二点我们可以得出要存两个数组算两个数组。
//我们以存 AB 两数组之和为例。首先求出 A 和 B 任意两数之和 sumAB，以 sumAB 为 key，sumAB 出现的次数为 value，存入 hashmap 中。
//然后计算 C 和 D 中任意两数之和的相反数 sumCD，在 hashmap 中查找是否存在 key 为 sumCD。
//算法时间复杂度为 O(n2)。
//
//作者：guo-sheng-fei
//链接：https://leetcode.cn/problems/4sum-ii/solution/chao-ji-rong-yi-li-jie-de-fang-fa-si-shu-xiang-jia/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
class SolutionLeetCode454 {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        HashMap<Integer,Integer> hashMap = new HashMap<>();
        int res = 0;
        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j <nums2.length ; j++) {
                int sumAB = nums1[i] + nums2[j];
                if (hashMap.containsKey(sumAB)){ //如果已经有相同的和在里面就让value+1
                    hashMap.put(sumAB,hashMap.get(sumAB)+1);
                }else { // 否则就加入一个新的和
                    hashMap.put(sumAB,1);
                }
            }
        }
        for (int i = 0; i < nums3.length; i++) {
            for (int j = 0; j < nums4.length; j++) {
                int sumCD = -(nums3[i] + nums4[j]);
                if (hashMap.containsKey(sumCD)){ // 如果CD组的相反数存在，那么他们相加就能得到0
                    res += hashMap.get(sumCD);  // 对于AB组的每一个和 CD组每复合一个都应该是相乘的概念
                }
            }
        }
        return res;
    }
}
